/*
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

 

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：

输入：x = 2.10000, n = 3
输出：9.26100
示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
 

提示：

-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104
 

注意：本题与主站 50 题相同：https://leetcode-cn.com/problems/powx-n/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

#include "../stdc++.h"

// 递归 - 分治
class Solution {
public:
    double myPow(double x, int exp) {
        long n = exp;
        if (x == 0) return 0;
        if (x == 1 || n == 0) return 1;
        double res{0};
        if (n > 0) {
            double t = myPow(x, n / 2);
            if (n % 2 == 1) {
                res = t * t * x;
            } else {
                res = t * t;
            }
        } else {
            double t = myPow(x, -n / 2);
            if (-n % 2 == 1) {
                res = t * t * x;
            } else {
                res = t * t;
            }
            res = 1 / res;
        }
        return res;
    }
};

// 快速幂
class Solution {
public:
    double myPow(double x, int n) {
        if (x == 1 || n == 0) return 1; // 特殊情况
        double ret = 1; // 运算结果
        /*
        *  将指数转成long类型
        *  防止当n=INT_MAX时，
        *  下面进行exp = -exp时溢出
        */
        long exp = long(n);
        // 若指数为负数，就转成换多个底数的倒数进行运算
        if (n < 0) {
            x = 1/ x;
            exp = -exp;
        }
        // 进行快速幂
        while (exp) {
            /*
            *  挨个将指数最低位和1进行位与
            *  若结果为1，则底数要乘一次
            *  若结果为0，说明二进制该位为0，不需要进行相乘
            */
            if (exp & 1) ret *= x;
            /*
            *  指数的二进制，从低位到高位每进一位
            *  底数就要在现在的基础上进行一次平方
            *  这样，x^9，指数为1001，计算到最高位的1时
            *  进了三位，则底数就变成了x^(2^3)，即x^8
            *  正好满足思路中所描述的表达式
            */
            x *= x;
            exp >>= 1;
        }
        return ret;
    }
};
